/*************************************************************************/
/*									 */
/*	Routines for displaying, building, saving and restoring trees	 */
/*	-------------------------------------------------------------	 */
/*									 */
/*************************************************************************/
#ifndef TREES
#define TREES

#include "defns.i"
#include "types.i"
#include "extern.i"
#include "getnames.h"
#include <string.h>
#include <malloc.h>
#define	Tab		"|   "
#define	TabSize		4
#define	Width		80	/* approx max width of printed trees */

/*  If lines look like getting too long while a tree is being
printed, subtrees are broken off and printed separately after
the main tree is finished	 */

short	Subtree;		/* highest subtree to be printed */
Tree	Subdef[100];		/* pointers to subtrees */

FILE	*TRf = 0, *fopen();	/* file pointer for tree i/o */
char	Fn[500];		/* file name */

void PrintTree(Tree T);
void Show(Tree T, short Sh);
void ShowBranch(short Sh, Tree T, DiscrValue v);
short MaxLine(Tree St);
void Indent(short Sh, char *Mark);
void SaveTree(Tree T, String Extension);
void OutTree(Tree T);
Tree GetTree(String Extension);
Tree InTree();
void StreamOut(String s, int n);
void StreamIn(String s, int n);
void ReleaseTree(Tree Node);
Tree Leaf(ItemCount *ClassFreq, ClassNo NodeClass, ItemCount Cases, ItemCount Errors);
void Sprout(Tree Node, DiscrValue Branches);
int TreeSize(Tree Node);
Tree CopyTree(Tree T);
void SaveDiscreteNames();
void RecoverDiscreteNames();

extern CString strTemp0, strTemp1, strTemp2, strTemp3;
/*************************************************************************/
/*									 */
/*	Display entire decision tree T					 */
/*									 */
/*************************************************************************/

void PrintTree(Tree T)
{
	short s;

	Subtree=0;
	vecstrOutput.push_back(_T("Decision Tree:\n"));
	Show(T, 0);
	vecstrOutput.push_back(_T("\n"));

	ForEach(s, 1, Subtree)
	{
		strTemp0.Format(_T("%d"),s);
		vecstrOutput.push_back(_T("\n\nSubtree [S")+strTemp0+_T("]\n"));
		Show(Subdef[s], 0);
		vecstrOutput.push_back(_T("\n"));
	}
	vecstrOutput.push_back(_T("\n"));
}



/*************************************************************************/
/*									 */
/*	Display the tree T with offset Sh				 */
/*									 */
/*************************************************************************/
void Show(Tree T, short Sh)
{
	DiscrValue v, MaxV;
	//short MaxLine();

	if ( T->NodeType )
	{
		/*  See whether separate subtree needed  */

		if ( T != Nil && Sh && Sh * TabSize + MaxLine(T) > Width )
		{
			if ( Subtree < 99 )
			{
				Subdef[++Subtree] = T;
				strTemp0.Format(_T("%d"),Subtree);
				vecstrOutput.push_back(_T("[S")+strTemp0+_T("]"));
			}
			else
			{
				vecstrOutput.push_back(_T("[S??]"));
			}
		}
		else
		{
			MaxV = T->Forks;

			/*  Print simple cases first */

			ForEach(v, 1, MaxV)
			{
				if ( ! T->Branch[v]->NodeType )
				{
					ShowBranch(Sh, T, v);
				}
			}

			/*  Print subtrees  */

			ForEach(v, 1, MaxV)
			{
				if ( T->Branch[v]->NodeType )
				{
					ShowBranch(Sh, T, v);
				}
			}
		}
	}
	else
	{
		strTemp0=ClassName[T->Leaf];
		strTemp1.Format(_T("%.1f"),T->Items);
		vecstrOutput.push_back(_T(" ") +strTemp0+ _T("(")+strTemp1);
		strTemp0.Format(_T("%.1f"),T->Errors);
		if ( T->Errors > 0 ) vecstrOutput.push_back(_T("/")+strTemp0);
		vecstrOutput.push_back(_T(")"));
	}
}



/*************************************************************************/
/*									 */
/*	Print a node T with offset Sh, branch value v, and continue	 */
/*									 */
/*************************************************************************/
void ShowBranch(short Sh, Tree T, DiscrValue v)
{
	DiscrValue Pv, Last;
	Attribute Att;
	Boolean FirstValue;
	short TextWidth, Skip, Values=0, i;

	Att = T->Tested;

	switch ( T->NodeType )
	{
	case BrDiscr:

		Indent(Sh, Tab);

		strTemp0=AttName[Att];
		strTemp1=AttValName[Att][v];
		vecstrOutput.push_back(strTemp0+_T(" = ")+strTemp1+_T(":"));
		break;

	case ThreshContin:

		Indent(Sh, Tab);

		strTemp0=AttName[Att];
		strTemp1=( v == 1 ? "<=" : ">" );
		strTemp2.Format(_T("%g"),T->Cut);
		vecstrOutput.push_back(strTemp0 + _T(" ") +strTemp1+ _T(" ")+ strTemp2);

		if ( T->Lower != T->Upper )
		{
			strTemp0.Format(_T("%g"), T->Lower);
			strTemp1.Format(_T("%g"), T->Upper);
			vecstrOutput.push_back(_T("[")+ strTemp0+_T(", ")+strTemp1+_T("]"));
		}

		vecstrOutput.push_back(_T(":"));
		break;

	case BrSubset:

		/*  Count values at this branch  */

		ForEach(Pv, 1, MaxAttVal[Att])
		{
			if ( In(Pv, T->Subset[v]) )
			{
				Last = Pv;
				Values++;
			}
		}
		if ( ! Values ) return;

		Indent(Sh, Tab);

		if ( Values == 1 )
		{
			strTemp0=AttName[Att];
			strTemp1=AttValName[Att][Last];
			vecstrOutput.push_back(strTemp0+_T(" = ")+strTemp1+_T(" :"));
			break;
		}
		strTemp0=AttName[Att];
		vecstrOutput.push_back(strTemp0+_T(" in {"));
		FirstValue = true;
		Skip = TextWidth = strlen(AttName[Att]) + 5;

		ForEach(Pv, 1, MaxAttVal[Att])
		{
			if ( In(Pv, T->Subset[v]) )
			{
				if ( ! FirstValue &&
					TextWidth + strlen(AttValName[Att][Pv]) + 11 > Width )
				{
					Indent(Sh, Tab);
					ForEach(i, 1, Skip) putchar(' ');

					TextWidth = Skip;
					FirstValue = true;
				}
				strTemp0=AttValName[Att][Pv];
				strTemp1=Pv == Last ? '}' : ',';
				vecstrOutput.push_back(strTemp0+strTemp1);
				TextWidth += strlen(AttValName[Att][Pv]) + 1;
				FirstValue = false;
			}
		}
		putchar(':');
	}

	Show(T->Branch[v], Sh+1);
}



/*************************************************************************/
/*									 */
/*	Find the maximum single line size for non-leaf subtree St.	 */
/*	The line format is						 */
/*			<attribute> <> X.xx:[ <class (<Items>)], or	 */
/*			<attribute> = <DVal>:[ <class> (<Items>)]	 */
/*									 */
/*************************************************************************/
short MaxLine(Tree St)
{
	Attribute a;
	DiscrValue v, MaxV, Next;
	short Ll, MaxLl=0;

	a = St->Tested;

	MaxV = St->Forks;
	ForEach(v, 1, MaxV)
	{
		Ll = ( St->NodeType == 2 ? 4 : strlen(AttValName[a][v]) ) + 1;

		/*  Find the appropriate branch  */

		Next = v;

		if ( ! St->Branch[Next]->NodeType )
		{
			Ll += strlen(ClassName[St->Branch[Next]->Leaf]) + 6;
		}
		MaxLl = Max(MaxLl, Ll);
	}

	return strlen(AttName[a]) + 4 + MaxLl;
}



/*************************************************************************/
/*								   	 */
/*	Indent Sh columns					  	 */
/*								  	 */
/*************************************************************************/
void Indent(short Sh, char *Mark)
{
	vecstrOutput.push_back(_T("\n"));
	strTemp0=Mark;
	while ( Sh-- ) vecstrOutput.push_back(strTemp0);
}



/*************************************************************************/
/*									 */
/*	Save entire decision tree T in file with extension Extension	 */
/*									 */
/*************************************************************************/

void SaveTree(Tree T, String Extension)
{
	static char *LastExt="";

	if ( strcmp(LastExt, Extension) )
	{
		LastExt = Extension;

		if ( TRf ) fclose(TRf);

		strcpy(Fn, FileName);
		strcat(Fn, Extension);
		if ( ! ( TRf = fopen(Fn, "w") ) )
			Error(0, Fn, " for writing");
	}

	putc('\n', TRf);
	OutTree(T);

	SaveDiscreteNames();
}



/*************************************************************************/
/*									 */
/*	Save tree T as characters					 */
/*									 */
/*************************************************************************/

void OutTree(Tree T)
{
	DiscrValue v;
	int Bytes;

	StreamOut((char *) &T->NodeType, sizeof(short));
	StreamOut((char *) &T->Leaf, sizeof(ClassNo));
	StreamOut((char *) &T->Items, sizeof(ItemCount));
	StreamOut((char *) &T->Errors, sizeof(ItemCount));
	StreamOut((char *) T->ClassDist, (MaxClass + 1) * sizeof(ItemCount));

	if ( T->NodeType )
	{
		StreamOut((char *) &T->Tested, sizeof(Attribute));
		StreamOut((char *) &T->Forks, sizeof(short));

		switch ( T->NodeType )
		{
		case BrDiscr:
			break;

		case ThreshContin:
			StreamOut((char *) &T->Cut, sizeof(float));
			StreamOut((char *) &T->Lower, sizeof(float));
			StreamOut((char *) &T->Upper, sizeof(float));
			break;

		case BrSubset:
			Bytes = (MaxAttVal[T->Tested]>>3) + 1;
			ForEach(v, 1, T->Forks)
			{
				StreamOut((char *) T->Subset[v], Bytes);
			}
			break;
		}

		ForEach(v, 1, T->Forks)
		{
			OutTree(T->Branch[v]);
		}
	}
}



/*************************************************************************/
/*									 */
/*	Retrieve entire decision tree with extension Extension		 */
/*									 */
/*************************************************************************/
Tree GetTree(String Extension)
{
	Tree Hold, InTree();
	static char *LastExt="";

	if ( strcmp(LastExt, Extension) )
	{
		LastExt = Extension;

		if ( TRf ) fclose(TRf);

		strcpy(Fn, FileName);
		strcat(Fn, Extension);
		if ( ! ( TRf = fopen(Fn, "r") ) ) Error(0, Fn, "");
	}

	if ( ! TRf || getc(TRf) == EOF ) return Nil;

	Hold = InTree();

	RecoverDiscreteNames();

	return Hold;
}



/*************************************************************************/
/*									 */
/*	Retrieve tree from saved characters				 */
/*									 */
/*************************************************************************/

Tree InTree()
{
	Tree T;
	DiscrValue v;
	int Bytes;

	T = (Tree) malloc(sizeof(TreeRec));

	StreamIn((char *) &T->NodeType, sizeof(short));
	StreamIn((char *) &T->Leaf, sizeof(ClassNo));
	StreamIn((char *) &T->Items, sizeof(ItemCount));
	StreamIn((char *) &T->Errors, sizeof(ItemCount));

	T->ClassDist = (ItemCount *) calloc(MaxClass+1, sizeof(ItemCount));
	StreamIn((char *) T->ClassDist, (MaxClass + 1) * sizeof(ItemCount));

	if ( T->NodeType )
	{
		StreamIn((char *) &T->Tested, sizeof(Attribute));
		StreamIn((char *) &T->Forks, sizeof(short));

		switch ( T->NodeType )
		{
		case BrDiscr:
			break;

		case ThreshContin:
			StreamIn((char *) &T->Cut, sizeof(float));
			StreamIn((char *) &T->Lower, sizeof(float));
			StreamIn((char *) &T->Upper, sizeof(float));
			break;

		case BrSubset:
			T->Subset = (Set *) calloc(T->Forks + 1, sizeof(Set));

			Bytes = (MaxAttVal[T->Tested]>>3) + 1;
			ForEach(v, 1, T->Forks)
			{
				T->Subset[v] = (Set) malloc(Bytes);
				StreamIn((char *) T->Subset[v], Bytes);
			}
		}

		T->Branch = (Tree *) calloc(T->Forks + 1, sizeof(Tree));
		ForEach(v, 1, T->Forks)
		{
			T->Branch[v] = InTree();
		}
	}

	return T;
}



/*************************************************************************/
/*									 */
/*	Stream characters to/from file TRf from/to an address		 */
/*									 */
/*************************************************************************/

void StreamOut(String s, int n)
{
	while ( n-- ) putc(*s++, TRf);
}


void StreamIn(String s, int n)
{
	while ( n-- ) *s++ = getc(TRf);
}



/*************************************************************************/
/*									 */
/*	Free up space taken up by tree Node				 */
/*									 */
/*************************************************************************/
void ReleaseTree(Tree Node)
{
	DiscrValue v;

	if ( Node->NodeType )
	{
		ForEach(v, 1, Node->Forks)
		{
			ReleaseTree(Node->Branch[v]);
		}

		free(Node->Branch);

		if ( Node->NodeType == BrSubset )
		{
			free(Node->Subset);
		}

	}

	free(Node->ClassDist);
	free(Node);
}



/*************************************************************************/
/*									 */
/*	Construct a leaf in a given node				 */
/*									 */
/*************************************************************************/

Tree Leaf(ItemCount *ClassFreq, ClassNo NodeClass, ItemCount Cases, ItemCount Errors)
{
	Tree Node;

	Node = (Tree) calloc(1, sizeof(TreeRec));

	Node->ClassDist = (ItemCount *) calloc(MaxClass+1, sizeof(ItemCount));
	memcpy(Node->ClassDist, ClassFreq, (MaxClass+1) * sizeof(ItemCount));

	Node->NodeType	= 0; 
	Node->Leaf		= NodeClass;
	Node->Items		= Cases;
	Node->Errors	= Errors;

	return Node; 
}



/*************************************************************************/
/*									 */
/*	Insert branches in a node 	                 		 */
/*									 */
/*************************************************************************/
void Sprout(Tree Node, DiscrValue Branches)
{
	Node->Forks = Branches;

	Node->Branch = (Tree *) calloc(Branches+1, sizeof(Tree));
}



/*************************************************************************/
/*									 */
/*	Count the nodes in a tree					 */
/*									 */
/*************************************************************************/
int TreeSize(Tree Node)
{
	int Sum=0;
	DiscrValue v;

	if ( Node->NodeType )
	{
		ForEach(v, 1, Node->Forks)
		{
			Sum += TreeSize(Node->Branch[v]);
		}
	}

	return Sum + 1;
}



/*************************************************************************/
/*									 */
/*	Return a copy of tree T						 */
/*									 */
/*************************************************************************/

Tree CopyTree(Tree T)
{
	DiscrValue v;
	Tree New;

	New = (Tree) malloc(sizeof(TreeRec));
	memcpy(New, T, sizeof(TreeRec));

	New->ClassDist = (ItemCount *) calloc(MaxClass+1, sizeof(ItemCount));
	memcpy(New->ClassDist, T->ClassDist, (MaxClass + 1) * sizeof(ItemCount));

	if ( T->NodeType )
	{
		New->Branch = (Tree *) calloc(T->Forks + 1, sizeof(Tree));
		ForEach(v, 1, T->Forks)
		{
			New->Branch[v] = CopyTree(T->Branch[v]);
		}
	}

	return New;
}



/*************************************************************************/
/*									 */
/*	Save attribute values read with "discrete N"			 */
/*									 */
/*************************************************************************/

void SaveDiscreteNames()
{
	Attribute Att;
	DiscrValue v;
	int Length;

	ForEach(Att, 0, MaxAtt)
	{
		if ( SpecialStatus[Att] != DISCRETE ) continue;

		StreamOut((char *) &MaxAttVal[Att], sizeof(int));

		ForEach(v, 1, MaxAttVal[Att])
		{
			Length = strlen(AttValName[Att][v]) + 1;

			StreamOut((char *) &Length, sizeof(int));
			StreamOut((char *) AttValName[Att][v], Length);
		}
	}
}



/*************************************************************************/
/*									 */
/*	Recover attribute values read with "discrete N"			 */
/*									 */
/*************************************************************************/
void RecoverDiscreteNames()
{
	Attribute Att;
	DiscrValue v;
	int Length;

	ForEach(Att, 0, MaxAtt)
	{
		if ( SpecialStatus[Att] != DISCRETE ) continue;

		StreamIn((String)&MaxAttVal[Att], sizeof(int));

		ForEach(v, 1, MaxAttVal[Att])
		{
			StreamIn((String)&Length, sizeof(int));

			AttValName[Att][v] = (char *) malloc(Length);
			StreamIn(AttValName[Att][v], Length);
		}
	}
}


#endif